{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Increasing Quadruplets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #array #dynamic-programming #enumeration #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #数组 #动态规划 #枚举 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countQuadruplets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计上升四元组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;，它包含&nbsp;<code>1</code>&nbsp;到&nbsp;<code>n</code>&nbsp;的所有数字，请你返回上升四元组的数目。</p>\n",
    "\n",
    "<p>如果一个四元组&nbsp;<code>(i, j, k, l)</code>&nbsp;满足以下条件，我们称它是上升的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i &lt; j &lt; k &lt; l &lt; n</code>&nbsp;且</li>\n",
    "\t<li><code>nums[i] &lt; nums[k] &lt; nums[j] &lt; nums[l]</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,3,2,4,5]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "- 当 i = 0 ，j = 1 ，k = 2 且 l = 3 时，有 nums[i] &lt; nums[k] &lt; nums[j] &lt; nums[l] 。\n",
    "- 当 i = 0 ，j = 1 ，k = 2 且 l = 4 时，有 nums[i] &lt; nums[k] &lt; nums[j] &lt; nums[l] 。\n",
    "没有其他的四元组，所以我们返回 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,2,3,4]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>只存在一个四元组 i = 0 ，j = 1 ，k = 2 ，l = 3 ，但是 nums[j] &lt; nums[k] ，所以我们返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>4 &lt;= nums.length &lt;= 4000</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= nums.length</code></li>\n",
    "\t<li><code>nums</code>&nbsp;中所有数字 <strong>互不相同</strong>&nbsp;，<code>nums</code>&nbsp;是一个排列。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-increasing-quadruplets](https://leetcode.cn/problems/count-increasing-quadruplets/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-increasing-quadruplets](https://leetcode.cn/problems/count-increasing-quadruplets/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2,4,5]', '[1,2,3,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        from sortedcontainers import SortedList\n",
    "        res = 0\n",
    "        lefts = SortedList(nums[:1])\n",
    "        for m1, nm1 in enumerate(nums[1:-2], 1):\n",
    "            nRights = nums[-1]>nm1\n",
    "            for m2 in range(N-2, m1, -1):\n",
    "                nm2 = nums[m2]\n",
    "                if nm2 > nm1:\n",
    "                    nRights += 1\n",
    "                    continue\n",
    "                res += nRights * lefts.bisect_right(nm2)\n",
    "            lefts.add(nm1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        l = []\n",
    "        dp = {}\n",
    "        ret = 0\n",
    "\n",
    "        for i, n in enumerate(nums):\n",
    "            p = bisect.bisect_left(l, n)\n",
    "\n",
    "            for i in range(p):\n",
    "                ret += dp[l[i]][2]\n",
    "\n",
    "            for i in range(p, len(l)):\n",
    "                dpi = dp[l[i]]\n",
    "                dpi[2] += bisect.bisect_left(dpi[1], n)\n",
    "\n",
    "            dp[n] = [1, l[:p], 0]\n",
    "            l.insert(p, n)\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        sl = SortedList()\n",
    "        cnts = Counter()\n",
    "        \n",
    "        dct = defaultdict(SortedList)\n",
    "\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            for k, v in cnts.items():\n",
    "                if x > k:\n",
    "                    ans += v\n",
    "                    \n",
    "            for k, v in dct.items():\n",
    "                if k > x:\n",
    "                    cnts[k] += v.bisect_right(x)\n",
    "            \n",
    "            for y in sl:\n",
    "                if y > x:\n",
    "                    break\n",
    "                dct[x].add(y)\n",
    "            \n",
    "            sl.add(x)\n",
    "            \n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "      \n",
    "        n=len(nums)\n",
    "        presmall=[[] for _ in range(n)]\n",
    "        pre=[nums[0]]\n",
    "        for i in range(1,n):\n",
    "            index=bisect.bisect_left(pre,nums[i])\n",
    "            presmall[i]=pre[:index]\n",
    "            bisect.insort(pre,nums[i])\n",
    "        afterbig=[[] for _ in range(n)]\n",
    "        after=[nums[n-1]]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            index=bisect.bisect_left(after,nums[i])\n",
    "            if index<len(after):\n",
    "                afterbig[i]=after[index:]            \n",
    "            bisect.insort(after,nums[i])\n",
    "        res=0\n",
    "        # jk=[]\n",
    "        for j in range(n):\n",
    "            for k in range(j+1,n):\n",
    "                if nums[j]>nums[k]:\n",
    "                    index=bisect.bisect_left(presmall[j],nums[k])\n",
    "                    if index>0:\n",
    "                        lndex=bisect.bisect_left(afterbig[k],nums[j])\n",
    "                        res+=index*(len(afterbig[k])-lndex)                           \n",
    "                    # jk.append((j,k))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        left = SortedList()\n",
    "        left.add(nums[0])\n",
    "        rrr = [0]*n\n",
    "        right = SortedList()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            right.add(nums[i])\n",
    "            rrr[i] = right.copy()\n",
    "        for i in range(1,n-2):\n",
    "            for j in range(n-2,i,-1):\n",
    "                if nums[i] > nums[j]:\n",
    "                    res += left.bisect_left(nums[j])*(len(rrr[j])-rrr[j].bisect_right(nums[i]))\n",
    "            left.add(nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = sortedcontainers.SortedList()\n",
    "        s.add(nums[0])\n",
    "        sl = defaultdict(sortedcontainers.SortedList)\n",
    "        for j in range(n - 2, 1, -1):\n",
    "            sl[j] = sl[j + 1].copy()\n",
    "            sl[j].add(nums[j+1])\n",
    "        # print(sl)\n",
    "        ans = 0\n",
    "        for j in range(1, n - 2):\n",
    "            for k in range(j + 1, n - 1):\n",
    "                if nums[k] < nums[j]:\n",
    "                    i = s.bisect(nums[k])\n",
    "                    l = sl[k].bisect(nums[j])\n",
    "                    ans += i * (len(sl[k]) - l)\n",
    "                    # print(j, k, s, sl, i, l, ans)\n",
    "            s.add(nums[j])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        prefix = [sorted(nums[:i + 1]) for i in range(n)]  # prefix[i]: sorted(nums[:i + 1])\n",
    "        suffix = [sorted(nums[i:]) for i in range(n)]  # suffix[i]: sorted(nums[i:])\n",
    "        \n",
    "        ans = 0\n",
    "        # 遍历满足nums[j] > nums[k]的(j, k)二元组\n",
    "        for j in range(1, n - 2):\n",
    "            for k in range(j + 1, n - 1):\n",
    "                if nums[j] > nums[k]:\n",
    "                    tmp1 = bisect_left(prefix[j - 1], nums[k])  # prefix[j - 1]中有多少个数小于nums[k]\n",
    "                    tmp2 = n - (k + 1) - bisect_left(suffix[k + 1], nums[j])  # suffix[k + 1]中有多少个数大于nums[j]\n",
    "                    ans += tmp1 * tmp2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        # nums = sorted(range(4000), key = lambda x: random.random())\n",
    "        def sortedprefix(ls):\n",
    "            cur = []\n",
    "            res = [cur]\n",
    "            for i in ls:\n",
    "                cur = cur.copy()\n",
    "                bisect.insort(cur, i)\n",
    "                res.append(cur)\n",
    "            return res\n",
    "        L = sortedprefix(nums)\n",
    "        R = sortedprefix(reversed(nums))\n",
    "        R.reverse()\n",
    "        N = len(nums)\n",
    "        res = 0\n",
    "        for k in range(N):\n",
    "            for j in range(k):\n",
    "                if nums[k]<nums[j]:\n",
    "                    # i<j, l>k, nums[i]<nums[k], nums[]\n",
    "                    icount = bisect.bisect(L[j], nums[k])\n",
    "                    lcount = len(R[k]) - bisect.bisect(R[k], nums[j])\n",
    "                    res += icount*lcount\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        s1 = [[]]\n",
    "        s2 = [[]]\n",
    "        for j in range(1,n):\n",
    "            s1.append(sorted(nums[:j]))\n",
    "        for j in range(n-1,-1,-1):\n",
    "            s2.append(sorted(nums[j:]))\n",
    "        # print(s1,s2)\n",
    "        for j in range(1,n):\n",
    "            for k in range(j+1,n-1):\n",
    "                if nums[k] < nums[j]:\n",
    "                    x = bisect.bisect(s1[j],nums[k])\n",
    "                    y = len(s2[n-k-1]) - bisect.bisect(s2[n-k-1], nums[j])\n",
    "                    # print(j,k)\n",
    "                    ans += x*y\n",
    "                    # print(x,y)\n",
    "        return ans\n",
    "                    \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        note1 = [[0] * n for _ in range(n)]\n",
    "        for k in range(2, n-1):\n",
    "            cnt = sum(nums[k] > nums[i] for i in range(k))\n",
    "            for j in range(k-1, 0, -1):\n",
    "                if nums[j] > nums[k]: note1[j][k] = cnt\n",
    "                else: cnt -= 1\n",
    "                    \n",
    "        ans = 0      \n",
    "        for j in range(1, n-2):\n",
    "            cnt = sum(nums[l] > nums[j] for l in range(j+1, n))\n",
    "            for k in range(j+1, n-1):\n",
    "                if nums[j] > nums[k]: \n",
    "                    ans += cnt * note1[j][k] \n",
    "                else: \n",
    "                    cnt -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef countQuadruplets(self, nums: List[int]) -> int:\n",
    "\t\tn=len(nums)\n",
    "\t\tijks=[[0 for i in range(n)] for j in range(n)]\n",
    "\t\tfor k in range(n):\n",
    "\t\t\tpre_sum=0\n",
    "\t\t\tfor j in range(k):\n",
    "\t\t\t\tif nums[j] > nums[k]:\n",
    "\t\t\t\t\tijks[j][k]=pre_sum\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tpre_sum+=1\n",
    "\t\tans=0\n",
    "\t\tfor j in range(n):\n",
    "\t\t\tsuf_sum=0\n",
    "\t\t\tfor k in range(n-1-j):\n",
    "\t\t\t\tif nums[n-1-k] > nums[j]:\n",
    "\t\t\t\t\tsuf_sum+=1\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tans+=ijks[j][n-1-k]*suf_sum\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        left = [[]]\n",
    "        for i in range(1, len(nums)):\n",
    "            left.append(sorted(left[-1] + [nums[i - 1]]))\n",
    "        right = [[]]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            right.append(sorted(right[-1] + [nums[i + 1]]))\n",
    "        right = right[::-1]\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums) - 2):\n",
    "            for j in range(i + 1, len(nums) - 1):\n",
    "                if nums[i] < nums[j]: continue\n",
    "                l = bisect_right(left[i], nums[j])\n",
    "                r = len(right[j]) - bisect_right(right[j], nums[i])\n",
    "                ans += l * r\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        had = [[0] * n for _ in range(n)]\n",
    "        pre = [0] * n\n",
    "        suf = [0] * n\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]:\n",
    "                    pre[i] += 1\n",
    "\n",
    "            suf[i] = (n - nums[i]) - (i - pre[i])         \n",
    "\n",
    "        for k in range(n-1):\n",
    "            less_k = 0\n",
    "            for j in range(k-1, 0, -1):\n",
    "                if nums[j] > nums[k]:\n",
    "                    p1 = pre[k] - less_k\n",
    "                    had[j][k] = pre[k] - less_k\n",
    "                else:\n",
    "                    less_k += 1\n",
    "\n",
    "        ans = 0\n",
    "        for j in range(n-3, 0, -1):\n",
    "            large_j = 0\n",
    "            \n",
    "            for k in range(j+1, n-1):\n",
    "                if nums[k] < nums[j]:\n",
    "                    ans += had[j][k] * (suf[j] - large_j)\n",
    "                else:\n",
    "                    large_j += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "class Solution:\n",
    "\tdef countQuadruplets(self, nums):\n",
    "\t\tn = len(nums)\n",
    "\t\tloc = {num: i for i, num in enumerate(nums)}\n",
    "\t\tans = 0\n",
    "\t\tleft = [[0] * n for _ in range(n)]\n",
    "\t\tss = SortedSet(range(1, n + 1))\n",
    "\t\tss.remove(nums[0])\n",
    "\t\tfor i in range(1, n - 2):\n",
    "\t\t\tss.remove(nums[i])\n",
    "\t\t\tlast = 0\n",
    "\t\t\tcnt = 0\n",
    "\t\t\tfor num in ss:\n",
    "\t\t\t\tcnt += num - last - 1\n",
    "\t\t\t\tlast = num\n",
    "\t\t\t\tif num > nums[i]:\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\t\tleft[i][loc[num]] = cnt\n",
    "\t\tss = SortedSet(range(-n, 0))\n",
    "\t\tss.remove(-nums[-1])\n",
    "\t\tfor i in range(n - 2, 1, -1):\n",
    "\t\t\tss.remove(-nums[i])\n",
    "\t\t\tlast = n + 1\n",
    "\t\t\tcnt = 0\n",
    "\t\t\tfor num in ss:\n",
    "\t\t\t\tcnt += last + num - 1\n",
    "\t\t\t\tlast = -num\n",
    "\t\t\t\tif -num < nums[i]:\n",
    "\t\t\t\t\tbreak\n",
    "\t\t\t\tans += left[loc[-num]][i] * cnt\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:  \n",
    "    def countQuadruplets(self, nums: List[int]) -> int:  \n",
    "        n = len(nums)  \n",
    "        z = [[0] * n for i in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            t = 0\n",
    "            for j in range(n-1, i, -1):\n",
    "                z[i][j] = t\n",
    "                if nums[j] > x:\n",
    "                    t += 1\n",
    "        r = 0\n",
    "        for j in range(n):\n",
    "            x = nums[j]\n",
    "            t = 0\n",
    "            for i in range(j):\n",
    "                if nums[i] > nums[j]:\n",
    "                    r += t * z[i][j]\n",
    "                if nums[i] < x:\n",
    "                    t += 1\n",
    "        return r "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        def print_table(table,name=\"\"):\n",
    "            print(\"=\"*40)\n",
    "            print(name)\n",
    "            for val in reversed(range(1,n+1)):\n",
    "                print(val,end=\": \")\n",
    "                for idx in range(n):\n",
    "                    print(table[idx, val],end=\", \")\n",
    "                print()\n",
    "            print(end=\" \"*2)\n",
    "            for idx in range(n):\n",
    "                print(\"[%d]\"%idx,end=\"\")\n",
    "            print()\n",
    "\n",
    "        _DEBUG=False\n",
    "        n = len(nums)\n",
    "        myint = np.intp\n",
    "        ans = 0\n",
    "        \n",
    "        pre_le_idx_val = np.zeros(shape=(n,n+2),dtype=myint)\n",
    "        for idx in range(1,n):\n",
    "            pre_le_idx_val[idx] = pre_le_idx_val[idx-1]\n",
    "            val = nums[idx-1]\n",
    "            pre_le_idx_val[idx, val+1:n+1] += 1\n",
    "        if _DEBUG:\n",
    "            print_table(pre_le_idx_val,\"pre\")\n",
    "\n",
    "        next_ge_idx_val = np.zeros(shape=(n,n+2),dtype=myint)\n",
    "        for idx in reversed(range(0,n-1)):\n",
    "            next_ge_idx_val[idx] = next_ge_idx_val[idx+1]\n",
    "            val = nums[idx+1]\n",
    "            next_ge_idx_val[idx, 1:val] += 1\n",
    "        if _DEBUG:\n",
    "            print_table(next_ge_idx_val,\"next\")\n",
    "        \n",
    "        ans = sum(\n",
    "            pre_le_idx_val[j, nums[k]] * next_ge_idx_val[k, nums[j]] \n",
    "            # pre_le_idx_val[j, nums[k]] * (n-nums[j]-(k-1-pre_le_idx_val[k, nums[j]]))\n",
    "            for k in range(2,n)\n",
    "            for j in range(1,k) \n",
    "            if nums[k] < nums[j]\n",
    "        )\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        left = [[0 for i in range(len(nums) + 1)] for i in range(len(nums) + 1)]\n",
    "        exist = [False] * (len(nums) + 1)\n",
    "        for i in range(len(nums)):\n",
    "            cnt = 0\n",
    "            exist[nums[i]] = True\n",
    "            for j in range(1, nums[i]):\n",
    "                left[nums[i]][j] = cnt\n",
    "                cnt += exist[j]\n",
    "\n",
    "        exist = [False] * (len(nums) + 1)\n",
    "        ans = 0\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            cnt = 0\n",
    "            exist[nums[i]] = True\n",
    "            right = [0] * (len(nums) + 1)\n",
    "            for j in range(len(nums), nums[i], -1):\n",
    "                right[j] = cnt\n",
    "                cnt += exist[j]\n",
    "            for j in range(i):\n",
    "                if nums[j] > nums[i]:\n",
    "                    ans += left[nums[j]][nums[i]] * right[nums[j]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "\n",
    "        m1 = [[0] * n for _ in range(n)]\n",
    "        for j in range(1, n-2):\n",
    "            cnt = 0\n",
    "            for l in range(j+1, n):\n",
    "                if nums[l] > nums[j]:\n",
    "                    cnt += 1\n",
    "            for k in range(j+1, n-1):\n",
    "                if nums[j] > nums[k]:\n",
    "                    m1[j][k] = cnt\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "        \n",
    "        m2 = [[0] * n for _ in range(n)]\n",
    "        for k in range(2, n-1):\n",
    "            cnt = 0\n",
    "            for i in range(k):\n",
    "                if nums[i] < nums[k]:\n",
    "                    cnt += 1\n",
    "            for j in range(k-1, 0, -1):\n",
    "                if nums[j] > nums[k]:\n",
    "                    m2[j][k] = cnt\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "        \n",
    "        for x in range(1, n-2):\n",
    "            for y in range(x+1, n-1):\n",
    "                res += m1[x][y] * m2[x][y]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        p = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                p[i][j+1] = p[i][j]\n",
    "                if nums[j] < nums[i]:\n",
    "                    p[i][j+1] += + 1\n",
    "            for j in range(n-1, i, -1):\n",
    "                p[i][j-1] = p[i][j]\n",
    "                if nums[j] > nums[i]:\n",
    "                    p[i][j-1] += 1\n",
    "        \n",
    "        #print(p)\n",
    "        ans = 0\n",
    "        for i in range(1, n-2):\n",
    "            for j in range(i+1, n-1):\n",
    "                if nums[i] > nums[j]:\n",
    "                    ans += p[j][i] * p[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = [[0]*(n+1) for _ in range(n+1)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i):\n",
    "                if nums[j] < nums[i]: cnt += 1\n",
    "                s[i][j] = cnt\n",
    "            cnt = 0\n",
    "            for j in range(n-1, i, -1):\n",
    "                if nums[j] > nums[i]: cnt += 1\n",
    "                s[i][j] = cnt\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(1, n-2):\n",
    "            for j in range(i+1, n-1):\n",
    "                if nums[i] > nums[j]:\n",
    "                    ans += s[j][i-1] * s[i][j+1]\n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        lessDict = defaultdict(list)\n",
    "        for i in range(N):\n",
    "            v = nums[i]\n",
    "            count = 0\n",
    "            for j in range(i):\n",
    "                if nums[j] < v:\n",
    "                    count += 1\n",
    "                lessDict[v].append(count)\n",
    "        moreDict = defaultdict(list)\n",
    "        for i in range(N-1, -1, -1):\n",
    "            v = nums[i]\n",
    "            count = 0\n",
    "            for j in range(N-1, i, -1):\n",
    "                if nums[j] > v:\n",
    "                    count += 1\n",
    "                moreDict[v].append(count)\n",
    "        # print(moreDict, lessDict)\n",
    "        rst = 0\n",
    "        for i in range(1, N-2):\n",
    "            for j in range(i+1, N-1):\n",
    "                if nums[i] > nums[j]:\n",
    "                    arr1 = lessDict[nums[j]]\n",
    "                    arr2 = moreDict[nums[i]]\n",
    "                    if len(arr1) >= i and len(arr2) >= N-j-1:\n",
    "                        rst += arr1[i-1]*arr2[N-j-2]\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        less_cnt = [[0] * n for _ in range(n)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(n):\n",
    "                if j:\n",
    "                    less_cnt[i][j] = less_cnt[i][j - 1]\n",
    "                if nums[i] > nums[j]:\n",
    "                    less_cnt[i][j] += 1\n",
    "        \n",
    "        result = 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            has = 0\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[j] < nums[i]:\n",
    "                    has += less_cnt[j][i]\n",
    "                else:\n",
    "                    result += has\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countQuadruplets(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        great = [0] * n\n",
    "        great[-1] = [0] * (n + 1)\n",
    "\n",
    "        for k in range(n-2, 0, -1):\n",
    "            great[k] = great[k+1][:]\n",
    "            for x in range(1, nums[k+1]):\n",
    "                great[k][x] += 1\n",
    "        \n",
    "        less = [0] * (n + 1)\n",
    "        res = 0\n",
    "        for j in range(1, n-1):\n",
    "            for x in range(nums[j-1]+1, n+1):\n",
    "                less[x] += 1\n",
    "            for k in range(j+1, n-1):\n",
    "                if nums[j] > nums[k]:\n",
    "                    res += less[nums[k]] * great[k][nums[j]]\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
